package boll;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception { new Main(); }
	
	public Main() throws Exception {
		List<Node> list = new ArrayList<Node>();
		List<String[]> pairs = new ArrayList<String[]>();
		
		// read words
/*		String str;
		int i=0;
		while ((str = r.readLine()) != null) {
			Node n = new Node();
			n.word = str;
			list.add(n);
			System.out.println(n.word +" "+ i++);
		}*/
		
		int words=5757;
		Scanner scan = new Scanner(new File("words-"+ words +".dat"));
		while (scan.hasNext()) {
			String s = scan.next();
			Node n = new Node();
			n.word = s;
			list.add(n);
		}
		scan = new Scanner(new File("words-"+ words +"-test.in"));
		while (scan.hasNext()) {
			String[] s = scan.nextLine().split(" ");
			pairs.add(s);
		}
		
		// make graph
		for (Node n: list) {
			n.paths = new ArrayList<Node>();
			for (Node m: list) {
				if (!n.word.equals(m.word) && match(n, m)) {
					n.paths.add(m);
				}
			}
		}
		
		/*for (Node n: list) {
			System.out.println(n.toStringAssoc());
		}*/
		
		// BFS
		for (String[] pair: pairs) {
			System.out.println(find(pair, list));
		}
	}
	
	private int find(String[] pair, List<Node> list) {
		List<Node> visited = new ArrayList<Node>();
		List<Node> que = new ArrayList<Node>();
		List<Node> childQue = new ArrayList<Node>();
		Node node=null, search=null;
		for (Node n: list) {
			if (n.word.equals(pair[0])) {
				node = n;
			} 
			if (n.word.equals(pair[1])) {
				search = n;
			}
		}
	
		int depth=0;
		que.add(node);
		while (!que.isEmpty() || !childQue.isEmpty()) {
			if (que.isEmpty()) {
				++depth;
				que = new ArrayList<Node>(childQue);
				childQue.clear();
			}
			if (visited.contains(que.get(0))) {
				que.remove(0);
				continue;
			}
			Node n = que.get(0);
			visited.add(n);
			if (n.word.equals(search.word)) {
				return depth;
			} else {
				childQue.addAll(n.paths);
			}
		}
		return -1;
	}
	
	private boolean match(Node n, Node m) {
		String s = m.word;
		
		for (int i=1; i<5; ++i) { 
			if (!s.contains(""+ n.word.charAt(i))) {
				return false;
			} else {
				s = s.replaceFirst(""+n.word.charAt(i), "\0");
			}
		}
		return true;
	}
}

class Node {
	public String word;
	public List<Node> paths;
	public int dbug;
	
	public String toString() {
		return word;
	}
	public String toStringAssoc() {
		String s = word +": ";
		for (Node n: paths) {
			s += n.word +", ";
		}
		return s;
	}
}
